home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / CompactIntArray.java < prev    next >
Text File  |  1998-09-22  |  15KB  |  419 lines
  1. /*
  2.  * @(#)CompactIntArray.java    1.10 97/10/28
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. /**
  34.  * class CompactATypeArray : use only on primitive data types
  35.  * Provides a compact way to store information that is indexed by Unicode
  36.  * values, such as character properties, types, keyboard values, etc.This
  37.  * is very useful when you have a block of Unicode data that contains
  38.  * significant values while the rest of the Unicode data is unused in the
  39.  * application or when you have a lot of redundance, such as where all 21,000
  40.  * Han ideographs have the same value.  However, lookup is much faster than a
  41.  * hash table.
  42.  * A compact array of any primitive data type serves two purposes:
  43.  * <UL type = round>
  44.  *     <LI>Fast access of the indexed values.
  45.  *     <LI>Smaller memory footprint.
  46.  * </UL>
  47.  * A compact array is composed of a index array and value array.  The index
  48.  * array contains the indicies of Unicode characters to the value array.
  49.  *
  50.  * @see                CompactShortArray
  51.  * @see                CompactByteArray
  52.  * @see                CompactCharArray
  53.  * @see                CompactStringArray
  54.  * @version            1.10 10/28/97
  55.  * @author             Helena Shih
  56.  */
  57. final class CompactIntArray implements Cloneable {
  58.  
  59.  
  60.     /**
  61.      * The total number of Unicode characters.
  62.      */
  63.     public static  final int UNICODECOUNT =65536;
  64.  
  65.     /**
  66.      * Default constructor for CompactIntArray, the default value of the
  67.      * compact array is 0.
  68.      */
  69.     public CompactIntArray()
  70.     {
  71.         this(0);
  72.     }
  73.     /**
  74.      * Constructor for CompactIntArray.
  75.      * @param defaultValue the default value of the compact array.
  76.      */
  77.  
  78.     public CompactIntArray(int defaultValue)
  79.     {
  80.         int i;
  81.         values = new int[UNICODECOUNT];
  82.         indices = new short[INDEXCOUNT];
  83.         for (i = 0; i < UNICODECOUNT; ++i) {
  84.             values[i] = defaultValue;
  85.         }
  86.         for (i = 0; i < INDEXCOUNT; ++i) {
  87.             indices[i] = (short)(i<<BLOCKSHIFT);
  88.         }
  89.         isCompact = false;
  90.     }
  91.  
  92.     /**
  93.      * Constructor for CompactIntArray.
  94.      * @param indexArray the indicies of the compact array.
  95.      * @param newValues the values of the compact array.
  96.      * @exception IllegalArgumentException If the index is out of range.
  97.      */
  98.     public CompactIntArray(short indexArray[],
  99.                            int newValues[])
  100.     {
  101.         int i;
  102.         if (indexArray.length != INDEXCOUNT)
  103.             throw new IllegalArgumentException("Index out of bounds.");
  104.         for (i = 0; i < INDEXCOUNT; ++i) {
  105.             short index = indexArray[i];
  106.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  107.                 throw new IllegalArgumentException("Index out of bounds.");
  108.         }
  109.         indices = indexArray;
  110.         values = newValues;
  111.     }
  112.  
  113.     /**
  114.      * Get the mapped value of a Unicode character.
  115.      * @param index the character to get the mapped value with
  116.      * @return the mapped value of the given character
  117.      */
  118.     public int elementAt(char index) // parameterized on short
  119.     {
  120.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  121.                        + (index & BLOCKMASK)]);
  122.     }
  123.  
  124.     /**
  125.      * Set a new value for a Unicode character.
  126.      * Set automatically expands the array if it is compacted.
  127.      * @param index the character to set the mapped value with
  128.      * @param value the new mapped value
  129.      */
  130.     public void setElementAt(char index, int value)
  131.     {
  132.         if (isCompact)
  133.             expand();
  134.         values[(int)index] = value;
  135.     }
  136.  
  137.     /**
  138.      * Set new values for a range of Unicode character.
  139.      * @param start the starting offset of the range
  140.      * @param end the ending offset of the range
  141.      * @param value the new mapped value
  142.      */
  143.     public void setElementAt(char start, char end, int value)
  144.     {
  145.         int i;
  146.         if (isCompact) {
  147.             expand();
  148.         }
  149.         for (i = start; i <= end; ++i) {
  150.             values[i] = value;
  151.         }
  152.     }
  153.  
  154.     /**
  155.       *Compact the array.
  156.       */
  157.     public void compact()
  158.     {
  159.         if (isCompact == false) {
  160.             char[] tempIndex;
  161.             int    tempIndexCount;
  162.             int[]  tempArray;
  163.             int    iBlock, iIndex;
  164.  
  165.             // make temp storage, larger than we need
  166.             tempIndex = new char[UNICODECOUNT];
  167.             // set up first block.
  168.             tempIndexCount = BLOCKCOUNT;
  169.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  170.                 tempIndex[iIndex] = (char)iIndex;
  171.             }; // endfor (iIndex = 0; .....)
  172.             indices[0] = (short)0;
  173.  
  174.             // for each successive block, find out its first position
  175.             // in the compacted array
  176.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  177.                 int     newCount, firstPosition, block;
  178.                 block = iBlock<<BLOCKSHIFT;
  179.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  180.                 firstPosition = FindOverlappingPosition( block, tempIndex,
  181.                                                          tempIndexCount);
  182.  
  183.                 newCount = firstPosition + BLOCKCOUNT;
  184.                 if (newCount > tempIndexCount) {
  185.                     for (iIndex = tempIndexCount;
  186.                          iIndex < newCount;
  187.                          ++iIndex) {
  188.                         tempIndex[iIndex] = (char)
  189.                                             (iIndex - firstPosition + block);
  190.                     } // endfor (iIndex = tempIndexCount....)
  191.                     tempIndexCount = newCount;
  192.                 } // endif (newCount > tempIndexCount)
  193.                 indices[iBlock] = (short)firstPosition;
  194.             } // endfor (iBlock = 1.....)
  195.  
  196.             // now allocate and copy the items into the array
  197.             tempArray = new int[tempIndexCount];
  198.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  199.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  200.             }
  201.             values = null;
  202.             values = tempArray;
  203.             isCompact = true;
  204.         } // endif (isCompact != false)
  205.     }
  206.  
  207.     /** For internal use only.  Do not modify the result, the behavior of
  208.       * modified results are undefined.
  209.       */
  210.     public short getIndexArray()[]
  211.     {
  212.         return indices;
  213.     }
  214.     /** For internal use only.  Do not modify the result, the behavior of
  215.       * modified results are undefined.
  216.       */
  217.     public int getStringArray()[]
  218.     {
  219.         return values;
  220.     }
  221.     /**
  222.      * Overrides Cloneable
  223.      */
  224.     public Object clone()
  225.     {
  226.         try {
  227.             CompactIntArray other = (CompactIntArray) super.clone();
  228.             other.values = (int[])values.clone();
  229.             other.indices = (short[])indices.clone();
  230.             return other;
  231.         } catch (CloneNotSupportedException e) {
  232.             throw new InternalError();
  233.         }
  234.     }
  235.     /**
  236.      * Compares the equality of two compact array objects.
  237.      * @param obj the compact array object to be compared with this.
  238.      * @return true if the current compact array object is the same
  239.      * as the compact array object obj; false otherwise.
  240.      */
  241.     public boolean equals(Object obj) {
  242.         if (obj == null) return false;
  243.         if (this == obj)                      // quick check
  244.             return true;
  245.         if (getClass() != obj.getClass())         // same class?
  246.             return false;
  247.         CompactIntArray other = (CompactIntArray) obj;
  248.         for (int i = 0; i < UNICODECOUNT; i++) {
  249.             // could be sped up later
  250.             if (elementAt((char)i) != other.elementAt((char)i))
  251.                 return false;
  252.         }
  253.         return true; // we made it through the guantlet.
  254.     }
  255.  
  256.     /**
  257.      * Generates the hash code for the compact array object
  258.      */
  259.  
  260.     public int hashCode() {
  261.         int result = 0;
  262.         int increment = Math.min(3, values.length/16);
  263.         for (int i = 0; i < values.length; i+= increment) {
  264.             result = result * 37 + values[i];
  265.         }
  266.         return result;
  267.     }
  268.     // --------------------------------------------------------------
  269.     // package private
  270.     // --------------------------------------------------------------
  271.     void writeArrays()
  272.     {
  273.         int i;
  274.         int cnt = (values.length > 0) ? values.length :
  275.             values.length+UNICODECOUNT;
  276.         System.out.println("{");
  277.         for (i = 0; i < INDEXCOUNT-1; i++)
  278.         {
  279.             System.out.print("(short)"
  280.                              + (int)((indices[i] >= 0) ?
  281.                                      (int)indices[i] :
  282.                                      (int)(indices[i]+UNICODECOUNT))
  283.                              + ", ");
  284.             if (i != 0)
  285.                 if (i % 10 == 0)
  286.                     System.out.println();
  287.         }
  288.         System.out.println("(short)" +
  289.                            (int)((indices[INDEXCOUNT-1] >= 0) ?
  290.                                  (int)indices[i] :
  291.                                  (int)(indices[i]+UNICODECOUNT)) +
  292.                            " }");
  293.         System.out.println("{");
  294.         for (i = 0; i < cnt-1; i++)
  295.         {
  296.             System.out.print(values[i] + ", ");
  297.             if (i != 0)
  298.                 if (i % 16 == 0)
  299.                     System.out.println();
  300.         }
  301.         System.out.println(values[cnt-1] + " }");
  302.     }
  303.  
  304.     // Print char Array  : Debug only
  305.     void printIndex(short start, short count)
  306.     {
  307.         int i;
  308.         for (i = start; i < count; ++i)
  309.         {
  310.             System.out.println(i + " -> : " +
  311.                                (int)((indices[i] >= 0) ?
  312.                                      indices[i] :
  313.                                      indices[i] + UNICODECOUNT));
  314.         }
  315.         System.out.println();
  316.     }
  317.  
  318.     void printPlainArray(int start,int count, char[] tempIndex)
  319.     {
  320.         int iIndex;
  321.         if (tempIndex != null)
  322.         {
  323.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  324.             {
  325.                 System.out.print(" " + values[tempIndex[iIndex]]);
  326.             }
  327.         }
  328.         else
  329.         {
  330.             for (iIndex = start; iIndex < start + count; ++iIndex)
  331.             {
  332.                 System.out.print(" " + values[iIndex]);
  333.             }
  334.         }
  335.         System.out.println("    Range: start " + start + " , count " + count);
  336.     }
  337.  
  338.     // --------------------------------------------------------------
  339.     // private
  340.     // --------------------------------------------------------------
  341.     /**
  342.       * Expanded takes the array back to a 65536 element array
  343.       */
  344.     private void expand()
  345.     {
  346.         int i;
  347.         if (isCompact) {
  348.             int[]   tempArray;
  349.             tempArray = new int[UNICODECOUNT];
  350.             for (i = 0; i < UNICODECOUNT; ++i) {
  351.                 tempArray[i] = elementAt((char)i);
  352.             }
  353.             for (i = 0; i < INDEXCOUNT; ++i) {
  354.                 indices[i] = (short)(i<<BLOCKSHIFT);
  355.             }
  356.             values = null;
  357.             values = tempArray;
  358.             isCompact = false;
  359.         }
  360.     }
  361.  
  362.     // # of elements in the indexed array
  363.     private short capacity()
  364.     {
  365.         return (short)values.length;
  366.     }
  367.  
  368.     private int[] getArray()
  369.     {
  370.         return values;
  371.     }
  372.  
  373.     private int
  374.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  375.     {
  376.         int i;
  377.         short j;
  378.         short currentCount;
  379.  
  380.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  381.             printPlainArray(start, BLOCKCOUNT, null);
  382.             printPlainArray(0, tempIndexCount, tempIndex);
  383.         }
  384.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  385.             currentCount = (short)BLOCKCOUNT;
  386.             if (i + BLOCKCOUNT > tempIndexCount) {
  387.                 currentCount = (short)(tempIndexCount - i);
  388.             }
  389.             for (j = 0; j < currentCount; ++j) {
  390.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  391.             }
  392.             if (j == currentCount) break;
  393.         }
  394.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  395.             for (j = 1; j < i; ++j) {
  396.                 System.out.print(" ");
  397.             }
  398.             printPlainArray(start, BLOCKCOUNT, null);
  399.             System.out.println("    Found At: " + i);
  400.         }
  401.         return i;
  402.     }
  403.  
  404.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  405.     private static  final boolean DEBUGTRACE = false;
  406.     private static  final boolean DEBUGSMALL = false;
  407.     private static  final boolean DEBUGOVERLAP = false;
  408.     private static  final int DEBUGSMALLLIMIT = 30000;
  409.     private static  final int BLOCKSHIFT =7;
  410.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  411.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  412.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  413.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  414.  
  415.     private int[] values;  // char -> int (char parameterized int)
  416.     private short indices[];
  417.     private boolean isCompact;
  418. };
  419.